package com.fr.lintcode;

import java.util.Arrays;

import org.junit.Test;

/**
*作者：furong
*日期：2016年12月28日
*时间：下午3:45:12
*/
public class Q59 {
    /**
     * @param numbers: Give an array numbers of n integer
     * @param target : An integer
     * @return : return the sum of the three integers, the sum closest target.
     */
    public int threeSumClosest(int[] numbers, int target) {
        if (numbers == null || numbers.length < 3) {
            return -1;
        }
        Arrays.sort(numbers);
        int close = Integer.MIN_VALUE;
        int length = numbers.length;
        for (int i = 0; i < length - 2; i++) {
            for (int j = i + 1; j < length - 1; j++) {
                int k = length - 1;
                while (k > j) {
                    int rs = numbers[i] + numbers[j] + numbers[k];
                    if (Math.abs(close - target) > Math.abs(rs - target)) {
                        close = rs;
                    }
                    if (rs == target) {
                        return target;
                    } else if (rs > target) {
                        k--;
                    } else {
                        break;
                    }
                }
            }
        }
        return close;
    }

    @Test
    public void testA() {
        int[] numbers = { -1, 2, 1, -4 };
        int target = 1;
        System.out.println(threeSumClosest(numbers, target));
    }
}
